337E - Divisor Tree - CodeForces Solution

#include <cstdio>
#include <iostream>
#include <algorithm>
//#define IN
#define LL long long
using namespace std;

const int MAXN = 1e5 + 5, mo = 1e9 + 9, INF = 1e9;
int n;
LL a[MAXN], b[MAXN];

int fa[MAXN];

int c[MAXN], d[MAXN];
int calc (LL v) {
  int cnt = 0;
  for (LL i = 2; i * i <= v; ++i)
    while (v % i == 0) ++cnt, v /= i;
  if (v > 1) ++cnt;
  return cnt;
}

int ans = INF, vs, ct[MAXN], C, sm;
void dfs (int dep) {
  if (dep > n) {
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
      int v = d[i];
      if (v == 1 && !ct[i]) ++cnt;
      else cnt += v + 1;

      //cout << cnt << endl;
    }
    if (vs > 1) cnt += 1;
    
    //for (int i = 1; i <= n; ++i) cout << b[i] << " "; puts ("");
    //cout << cnt << endl;
    ans = min (ans, cnt);
    return ;
  }
  for (int i = dep + 1; i <= n; ++i)
    if (b[i] % a[dep] == 0) {
      b[i] /= a[dep], d[i] -= c[dep], ++ct[i];
      dfs (dep + 1);
      b[i] *= a[dep], d[i] += c[dep], --ct[i];
    }
  ++vs;
  dfs (dep + 1);
  --vs;
}

int main() {
#ifdef IN
  freopen ("x.in", "r", stdin);
  freopen ("x.out", "w", stdout);
#endif
  int i,j,k;
  scanf ("%d", &n);
  for (i = 1; i <= n; ++i) scanf ("%lld", &a[i]);
  /*
  if (n == 1) {
    if (calc (a[1]) == 1) printf ("1");
    else printf ("%d", calc (a[1]) + 1);
    return 0;
  }
  */
  sort (a + 1, a + n + 1), C = n;
  for (i = 1; i <= n; ++i) b[i] = a[i];
  for (i = 1; i <= n; ++i) c[i] = d[i] = calc (a[i]);
  dfs (1);
  //cout << calc (6) << endl;
  printf ("%d", ans);
  return 0;
}